package com.cuz.for2024;

public class T79 {
    public static void main(String[] args) {
        char[][] chars = {{'A', 'B', 'C', 'E'},
                {'S', 'F', 'C', 'S'},
                {'A', 'D', 'E', 'E'}};
         chars = new char[][]{{'a'}};
        System.out.println(new T79().exist(chars, "a"));
    }

    public boolean exist(char[][] board, String word) {
        int row = board.length;
        int col = board[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (exist(board,word,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }

    public boolean exist(char[][] board, String word, int i, int j, int c) {
        if (i<0||j<0||i>=board.length||j>=board[0].length){
            return false;
        }
        if (c==word.length()){
            return true;
        }
        if (board[i][j] != word.charAt(c)) {
           return false;
        }
        if (c==word.length()-1){
            return true;
        }
        char temp = board[i][j];
        board[i][j] = '#';
        boolean flag = exist(board, word, i + 1, j, c + 1)
                || exist(board, word, i - 1, j, c + 1)
                || exist(board, word, i, j - 1, c + 1)
                || exist(board, word, i, j + 1, c + 1);
        board[i][j] = temp;
        return flag;
    }
}
